package demo.kk.demo1;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

class Solution {

    public static void main(String[] args) {
        //  nums1 = [3,1,2], nums2 = [1,2,3]
//        int[] nums1 = {3, 1, 2};
//        int[] nums2 = {1, 2, 3};
//        System.out.println(new Solution().minSplitMerge(nums1, nums2));
        // nums1 = [1,1,2,3,4,5], nums2 = [5,4,3,2,1,1]
        int[] nums3 = {1, 1, 2, 3, 4, 5};
        int[] nums4 = {5, 4, 3, 2, 1, 1};
        System.out.println(new Solution().minSplitMerge(nums3, nums4));
    }


    public int minSplitMerge(int[] nums1, int[] nums2) {


        List<Integer> numList1 = new ArrayList<>();
        for (int num : nums1) {
            numList1.add(num);
        }

        int n = nums1.length;

        List<Integer> numList2 = new ArrayList<>();
        for (int num : nums2) {
            numList2.add(num);
        }

        if (numList1.equals(numList2)) {
            return 0;
        }

        Queue<List<Integer>> queue = new LinkedList<>();
        Set<List<Integer>> set = new HashSet<>();
        queue.offer(numList1);
        set.add(numList1);

        int depth = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 暴枚举所有场景
                List<Integer> list = queue.poll();
                for (int j = 0; j < n - 1; j++) {
                    for (int k = j + 1; k < n; k++) {
                        // 提取出子数组
                        List<Integer> subList = new ArrayList<>(list.subList(j, k));
                        // 再将剩下的数组变成一个新的数组
                        List<Integer> newLastList = new ArrayList<>();
                        newLastList.addAll(list.subList(0, j));
                        newLastList.addAll(list.subList(k, n));

                        // 然后将子数组 遍历插入到新数组中
                        for (int l = 0; l <= newLastList.size(); l++) {
                            List<Integer> newNewList = new ArrayList<>(newLastList);
                            newNewList.addAll(l, subList);
                            // 如果 新数组等于 numList2 则直接返回结果
                            if (newNewList.equals(numList2)) {
                                return depth + 1;
                            }

                            // 添加到队列中
                            if (!set.contains(newNewList)) {
                                set.add(newNewList);
                                queue.offer(newNewList);
                            }
                        }
                    }
                }
            }
            depth++;
        }
        return depth;
    }
}